package offer;

/**
 * @Author Elephas
 * @Date 2022/2/10
 **/
@FunctionalInterface
public interface ValidateStackSequences {
    boolean validateStackSequences(int[] pushed, int[] popped);
}
class ValidateStackSequencesImpl1 implements ValidateStackSequences{
    static final int[] TEST_01_PUSHED = new int[]{1,2,3,4,5};
    static final int[] TEST_01_POPPED = new int[]{4,5,3,2,1};
    public static void main(String[] args) {
        new ValidateStackSequencesImpl1().validateStackSequences(TEST_01_PUSHED,TEST_01_POPPED);
    }
    private int[] stack;
    private int top;
    @Override
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        int ptrPushed = 0, ptrPopped = 0;
        int stackSize = pushed.length;
        init(stackSize);
        while(ptrPushed < stackSize){
            if(isEmepty()){
                push(pushed[ptrPushed]);
                ptrPushed++;
            }else if(peek() == popped[ptrPopped]){
                pop();
                ptrPopped++;
            }else{
                push(pushed[ptrPushed]);
                ptrPushed++;
            }
        }
        while(!isEmepty() && peek() == popped[ptrPopped]){
            pop();
            ptrPopped++;
        }
        return isEmepty();
        // abcde, edcba
    }
    private void init(int stackSize){
        top = -1;
        stack = new int[stackSize];
    }
    private boolean isEmepty(){
        if(top == -1){
            return true;
        }else{
            return false;
        }
    }
    private int peek(){
        return stack[top];
    }
    private int pop(){
        return stack[top--];
    }
    private void push(int element){
        stack[++top] = element;
    }

}
